Skip to main content

Full text of "The Interface message processor for the ARPA computer network"

See other formats

'-B O L T B E R A N E K A N D N E W M A N NC 
C O N S U L T I N G 
R E S E A R C H 
Report No. 1966 
April 1970 
1 January 1970 to 31 March 1970 
Principal Investigator: 
Mr. Frank E. Heart 
Telephone (617) 491-1850, Ext. 470 
Sponsored by 
Advanced Research Projects Agency 
Effective Date: 2 .January 1969 
Expiration Date: 31 December 1970 
b!,a c t Amount: $2,013,492 
Title of Work.?---I-lkP__ 
Submitted to: 
Advanced Research Projects Agency 
Washington, D.C. 20301 
Attend'ion: Dr. L.G. Roberts 
Telephone (202) 697-8654 
------------------------------<page break>-----------------------------
'""B O L T B E R A N E K A N D N E W M A N NC 
C O N S U L T I N G 
Report No. 1966 
April 1970 
1 January 1970 to 31 March 1970 
Advanced Research Projects Agency 
Washington, D.C. 20301 
Attn: Dr. L.G. Roberts 
This research was supported by the Advanced Research Projects 
Agency of the Department of Defense under Contract No. DAHC-15- 
------------------------------<page break>-----------------------------
Report No. 1966 
Bolt Beranek and Newman Inc. 
INTRODUCTION ................ 1 
A. Retrofits ................. 4 
B. Modem Simulator .............. 5 
NETWORK TESTING ............... 7 
PHONE LINE TEST PROGRAM ............ 10 
------------------------------<page break>-----------------------------
Report No. 1966 
Bolt Beranek and Newman Inc. 
This report describes several aspects of our progress on 
the ARPA computer network during the first quarter of 1970: 
©Several minor changes and additions have been made to 
the operational program. In addition we have streamlined 
the program assembly process. Software activity during the 
quarter is described in Section 2. 
ewe have designed a modem simulator that allows six full 
duplex modem channels to be interconnected in various configura- 
tions for testing IMP topologies in the BBN test cell. The 
design of this simulator and the results of other hardware 
activity are described in Section 3. 
eDuring the first quarter, we conducted the first of our 
planned network tests in the field. A description of the test 
procedure and some of the preliminary results are discussed in 
Section 4. 
eA second phone line test program has been coded to allow 
the buffer size to be selected in advance. This program is 
described in Section 5. 
------------------------------<page break>-----------------------------
Report No. 1966 
Bolt Beranek and Newman Inc. 
A new version of the operational program was released on 
March 1. This program incorporates the cease-on-link mecha- 
nism that resulted from the Utah meeting and subsequent 
discussions with the Hosts. We explained this mechanism in 
the previous Quarterly Technical Report (No. 4). [A Host may 
send a cease-on-link message to its IMP at any time. Its IMP 
will then specially mark the next RFNM it returns on that link 
and deliver that RFNM as a cease-on-link message to the other 
Host. The link will then be unblocked.] It is for the Hosts 
to agree to heed this convention and regulate the flow of 
The program has been modified to allow a maximum of five 
modems and a maximum of three Hosts in its standard configura- 
tion; should a further increase be required, the program can 
be modified to handle four Hosts. 
During the last quarter, we had our first opportunity to 
make the multiple Host logic work. In addition to requiring 
minor changes to the main software, a number of changes were 
made in the statistics programs to reduce the required amount 
of table space. One such change was to consolidate the 
statistics of all the Hosts into a single set of Host tables. 
The status reporting feature was modified to include two 
Hosts and five modems. In addition, the status of the sense 
switches, measurement flags, memory protect switch and the num- 
ber of free buffers are now reported. We implemented the sense 
switch 2 feature that enables the use of the parameter change 
------------------------------<page break>-----------------------------
Report No. 1966 
Bolt Beranek and Newman In 
A major change was made in the method of assembling the 
operational program. This change has considerably speeded up 
the assembly process and permits patch free system releases. 
Previously, we edied..the-program-on---the-PDP-1, 
the.,DDP-516, and. listed the program-usingthe'-XDS9-4'0"bli'ne  
oDe-. d ayn.igh.t.. s e s s i on ) .- we r e.,,typ i c 
asse,m2.!y .... We'have now,modified--an'existing. assembler on the 
PDPrl to assemble 516 code, thus reducing the total assembly 
time to several hours and in addition, allowing a new system 
tape to be prepared via remote teletype. 
------------------------------<page break>-----------------------------
Report No. 1966 
Bolt Beranek and Newman Inc. 
During the last quarter, we received delivery from Honey- 
well of IMPs No. 5, 6, and 7; these were installed and tested 
in the BBN test cell. Testing revealed a number of minor pro- 
blems and, while these problems have, for the most part, been 
easily corrected, considerable effort has been expended iq 
ocating them and in working with Honeywell to have them cor- 
rected. As of this date, machines No. 5, 6, and 7 are operating 
correctly in the test cell. 
In late March, AT&T succeeded in providing a 50-kilobit 
circuit across the country. Io--5BBN)wesh''con - 
. UCLA._!.kdard IMPTST p.rogram'asunb'ewee' 
we..?incmmm-u.i.aLon_.ouer...ths--ine] In particular, we have 
encountered no problem in communicating over this line and are 
able to communicate with each of the other four sites in the 
network using the IMP teletype. Our preliminary experience 
indicates that there is no delay noticeable to a person at a 
'teletype in echoing single character messages back and forth 
across the country. 
A. Retrofits 
The original four IMPs were delivered with certain known 
deficiences, which will be remedied by field retrofits during 
the next quarter. These include the following: 
1) The original design of the auto restart, including time- 
delay relays, had inadequate reliability. An altogether new 
------------------------------<page break>-----------------------------
Report No. 1966 
Bolt Beranek and Newman Inc. 
design delivered with machine No. 7 has been tested and ap- 
pears to work satisfactorily. This design will be retrofitted 
to all machines. 
2) Machine No. 5 was the first IMP delivered with the rug- 
gedized control panel. All successive machines have been 
delivered with the new panel, which appears to be working 
satisfactorily. Ruggedized panels will be retrofitted to the 
four IMPs presently in the field. 
3) A problem existed with the status lights, causing lights 
which should have been off to be partially lit. This problem 
arose from operating the light driver transistors beyond 
their maximum voltage ratings. A new power supply for these 
drivers was installed and demonstrated in machine No. 7. This 
cured the difficulty, and machines No. 5 and 6 have been retro- 
fitted with the new supply. Field machines will also be retro- 
B. Modem Simulator 
The 50-kilobit room circuit (2 modems) in our test cell 
provides only one full duplex IMP-to-IMP connection to be made 
in the standard way. To test more complex configurations (in- 
volving more than two IMPs), modem interfaces were connected 
directly via special cables. This method was awkward and re- 
quired some temporary rewiring of the machines. To avoid this 
awkwardness and to facilitate a wider variety of situations 
for testing the operational program, a "modem simulator" box 
(that simulates six full-duplex communication circuits) is 
being designed and constructed. The IMPs will connect directly 
into this box via their standard modem cables. The box will 
------------------------------<page break>-----------------------------
Report No. 1966 
Bolt Beranek and Newman Inc. 
provide the interconnection between pairs of send and recelve 
signals and will also provide a common clock signal simulat- 
ing the modem send and receive clocks required by IMP modem 
------------------------------<page break>-----------------------------
Report No. 1966 
Bolt Beranek and Newman Inc. 
During the last quarter, we coDducted the first of several 
planned network tests on the initial four-node net connectin N 
UCLA, SRI, UCSB, and Utah. The UCLA computer center and the 
facilities developed by UCLA for processing network measure- 
ment information were made available to us for an extended 
period of time. In addition, UCLA prepared a stand-alone test 
program for the XDS Sigma-7 computer to help us in our testing. 
In this and subsequent reports, we will be describing our 
testing activities, along with any test results of interest. 
We do not, however, intend these tests to be merely systema- 
tic measurements of net capability. Rather, the tests will 
be used to determine the lim_is of performance and capabili- 
 ties under extreme loading conditions, real and simulated. 
From our initial testing we obtained a clearer picture of the 
network performance and, at high traffic loads, located a 
number of program bugs that were easily corrected_L  
The network can be described as a taut communication 
system in the sense that each message entering the net pro i 
ceeds directly to its destination. We observed that messages 
do not wander about the net, even at high traffic loads. The 
net easily handles sequences of single-character messages typed 
at the IMP teletype. In all our testing, the Host was prompt 
in handling messages and we observed no backup of traffic. We 
explored the variations in buffer occupancy when the upper limits 
for reassembly buffers and store and forward buffers were varied. 
We observed that two conditions appear to cause a large number 
of IMP buffers to be occupied when the traffic is heavy. One 
------------------------------<page break>-----------------------------
Report No. 1966 
Bolt Beranek and Newman Inc. 
condition is an insufficient supply of reassembly buffers at 
the destination IMP. A second condition is the use of multi- 
ple links by a Host (for fanning messages)  which causes a 
large part (or all) of the source IMP's store and forward 
buffers to be filled. 
There was no observed buildup of store and forward traf- 
fic at intermediate IMPs, except when the number of reassembly 
buffers at the destination was insufficient to handle the in- 
coming traffic. From our tests, it appears as if a limit of 
8 or 16 reassembly buffers is not sufficient to handle heavy 
traffic to the Host. A limit of 32 reassembly buffers (which 
is the current maximum) does appear to be sufficient. In our 
initial tests, the variation of the store and forward limit 
appeared primarily to affect the maximum rate at which traf- 
fic could flow from the Host. The limit on the number of store 
and forward buffers is currently set to 21. 
The most important change made to the IMP program as a 
result of network testing was the removal of a phase-lock 
condition between message transmission time and the timeout 
period. Although the presence of this phenomenon was known 
about in advance of the testing, the extent to which it af- 
fected the round-trip transit time had not been expected. In 
the original version of the program, a periodically-run time- 
out program was relied upon to start up, if possible, each 
process that had not been able to continue running earlier, 
for example, while waiting for an event to occur. Although 
this mechanism had been introduced primarily as a safety 
feature, it had the unplanned effect of causing the round-trip 
times to be multiples of the timeout period for the shorter 
singletpacket messages. This effect is no longer present in 
------------------------------<page break>-----------------------------
Report No. 1966 
Bolt Beranek and Newman Inc. 
the new system. The round-trip time now depends only upon mes- 
sage length, the route, the phone line bit rates, and the traf- 
fic load. 
A bug was discovered and fixed in the multiple Host logic 
in the Host routine. A multiplication table used in the rout- 
ing algorithm had not fully assembled. This produced a brief 
flurry of random routing whenever the quality on the phone 
lines decreased momentarily. The required table was patched 
into the program. 
In an alternate routing experiment (performed with the 
routing bug still present), 8000-bit messages were sent from 
UCLA to SRI on 60 links at the RFNM limited rate. The traf- 
fic on the Host line to the IMP was 'measured to be approximately 
80 kilobits/sec for this case, thus making essentially complete 
use of both circuits from UCLA to SRI. The Host line was 
tested at about- 300 kilobits/sec with different Host message 
lengths and no timing problems were noticed. 
------------------------------<page break>-----------------------------
Report No. 
Bolt Beranek and Newman Inc. 
Our first phone line test program was designed as a 
simple way to obtain raw data on the occurrence.of packets 
in error on the phone line using short 88-bit packets. This 
data was printed on the IMP teletype (in octal) and also 
stored in a histogram. However, certain properties of the 
recorded data, such as the cumulative packet error rate, 
were quite inconvenient to compute from the recorded data and 
were only poorly approximated from the histogram. Furthermore, 
we had no convenient way to obtain the characteristics of the 
phone line when larger packets were used. 
During the last quarter, a second phone line test program 
was written. This program permits the selection of packet 
size, over the range from 88 bits to 9288 bits. The program 
first counts the number of consecutive good packets (i.e., 
packets that contain no errors) and then counts the number of 
consecutive packets in error and so forth. However, the raw 
data is not recorded. A histogram is kept of runs without 
error and also of error bursts, both of which are typed out 
'(but not cleared) every ten minutes. In addition, the pro- 
gram computes the ratio of total good packets to bad packets 
for each ten-minute interval, along with the ratio of cumu- 
lative good to cumulative bad since the beginning of the test. 
The new program was designed to measure as many as three 
phone lines simultaneously. The phone line may be looped back, 
thus giving a two-way test of the line; or another copy of the 
test program may be loaded into a neighboring IMP to obtain two 
one-way line tests. 
------------------------------<page break>-----------------------------
Report No. 1966 
Bolt Beranek and Newman Inc. 
The line test program also measures the propagation delay 
time to within 0.1 msec accuracy. As part of its initiali- 
zation procedure, the line test program transmits a message 
to its neighbors, in which it includes the current time as 
well as other pieces of information such as the buffer size. 
The neighboring IMPs, if any, must all have the line test 
program loaded and in a waiting state. When the neighboring 
IMP receives the initialization message, its line test program 
starts and returns the received initialization time. When 
this message returns, the delay is easily calculated. 
In addition, the line test program may be stoppDd when- 
ever a phone line error occurs and, using DDT, the exact 
location of the bit errors may be determined. This technique 
is useful with moderate- to long-size packets to help in under- 
standing the structure of error patterns. The program actually 
checks the data and thus allows the performance of the error 
check register to be monitored. A separate recording is made 
if the data is ever incorrect and not detected by the check 
register. However, this event has never been observed to 
------------------------------<page break>-----------------------------
Secuty Classification 
(Security clas.ification of title, hod F of abstract arid indexin annotation mu.'t be entered when the overall report 
1. ORIGINATING ACTIVITY (Co.orate author) 
Bolt Beranek and Newman Inc. 
50 Moulton Street 
Cambridge, Massachusetts 02138 
4. DESCRIPTIVE NOTES ("¾pe of report and. inclusive dates) 
QUARTERLY TECHNICAL.REPORT NO. 5, 1 January 1970 to 31 March 1970 
5. AU THORIS)(First name, middie initial, last name) 
April 1970 14 
DAHC15- 69-C-0179 
Advanced Research Projects Agency 
Washington, D.C. 20301 
9b. OTHER REPORT NO(S) ('Any other numbers that may be assigned 
this report) 
,.ABSTRACT The basic function of the IMP computer network is to allow large 
existing time-shared (Host) computers with different system configura- 
tions to communicate with each other. Each IMP (Interface Message Pro- 
cessor) computer accepts messages for its Host from other Host computers 
and transmits messages from its Host to other Hosts. Since there will 
not always be a direct link between two Hosts that wish to communicate, 
individual IMPs will, from time to time, perform the function of trans- 
ferring a message between Hosts that are not directly connected. This 
then leads to the two basic IMP configurations interfacing between 
Host computers and acting as a message switcher in the IMP network. 
The message switching is performed as a store and forward operation. 
Each IMP adapts its message routine to the condition of those portions 
of the IMP network to which it is connected. IMPs regularly measure 
network performance and report in special messages to the network meas- 
!urement center. Provision of a tracing capability permits the net 
operation to be studied comprehensively. An automatic trouble reporting 
capability detects a variety of network difficulties and reports them 
to an interested Host. An IMP can throw away packets that it has re- 
ceived but .not yet acknowledged, transmitting packets to other IMPs at 
its own discretion. Self-contained network operation is designed to 
protect and deliver messages from the source Host to the destination 
DD .Fo.. 473 
------------------------------<page break>-----------------------------
Security Classification 
Computers and Communication 
Store and Forward Communication 
ARPA Computer Network 
Honeywell DDP-516 
Program Design -- IMP 
DD ,Løo?.1473 (*) 
$/N 0 0 -807-6821 Security Classification A-  409 
------------------------------<page break>-----------------------------